package LC;

import java.util.*;

/**
 * https://leetcode.com/problems/word-ladder/description/
 * Given two words (beginWord and endWord), and a dictionary's word list,
 * find the length of shortest transformation sequence from beginWord to endWord, such that:
 * Only one letter can be changed at a time.
 * Each transformed word must exist in the word list.
 * Note that beginWord is not a transformed word.
 * For example,
 * Given:
 * beginWord = "hit"
 * endWord = "cog"
 * wordList = ["hot","dot","dog","lot","log","cog"]
 * As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
 * return its length 5.
 * Note:
 * Return 0 if there is no such transformation sequence.
 * All words have the same length.
 * All words contain only lowercase alphabetic characters.
 * You may assume no duplicates in the word list.
 * You may assume beginWord and endWord are non-empty and are not the same.
 * UPDATE (2017/1/20):
 * The wordList parameter had been changed to a list of strings
 * (instead of a set of strings). Please reload the code definition to get the latest changes.
 */
public class LC_127_WordLadder_HashSet_Queue {
    public static void main(String[] args) {
        int ladderLength = Solution.ladderLength("hit", "cog", Arrays.asList("hot", "dot", "dog", "lot", "log", "cog"));
        System.out.println(ladderLength);
    }

    static class Solution {
        static int ladderLength(String beginWord, String endWord, List<String> wordList) {
            if (beginWord == null || endWord == null || beginWord.length() == 0 || endWord.length() == 0 || beginWord.length() != endWord.length())
                return 0;
            Set<String> set = new HashSet<>(wordList);
            if (set.contains(beginWord)) set.remove(beginWord);
            Queue<String> wordQueue = new LinkedList<>();
            int level = 1;
            int curnum = 1;
            int nextnum = 0;
            wordQueue.add(beginWord);
            while (!wordQueue.isEmpty()) {
                String word = wordQueue.poll();
                curnum--;
                for (int i = 0; i < word.length(); i++) {
                    char[] wordunit = word.toCharArray();
                    for (char j = 'a'; j <= 'z'; j++) {
                        wordunit[i] = j;
                        String temp = new String(wordunit);
                        if (set.contains(temp)) {
                            if (temp.equals(endWord)) return level + 1;
                            nextnum++;
                            wordQueue.add(temp);
                            set.remove(temp);
                        }
                    }
                }
                if (curnum == 0) {
                    curnum = nextnum;
                    nextnum = 0;
                    level++;
                }
            }
            return 0;
        }
    }
}
